class Solution(object):
    def largestMultipleOfThree(self, digits):
        total = sum(digits)
        n = len(digits)
        digits.sort(reverse=True)
        if total % 3 == 0:
            if digits[0] != 0:
                out = [str(num) for num in digits]
                return ''.join(out)
            else:
                return '0'
        else:
            if total % 3 == 1:
                for k in range(n - 1, -1, -1):
                    if digits[k] % 3 == 1:
                        digits = digits[: k] + digits[k + 1:]
                        if not digits:
                            return ''
                        if digits[0] != 0:
                            out = [str(num) for num in digits]
                            return ''.join(out)
                        else:
                            return '0'
                index = []
                for k in range(n - 1, -1, -1):
                    if digits[k] % 3 == 2:
                        index.append(k)
                        if len(index) == 2:
                            index.reverse()
                            digits = digits[: index[0]] + digits[index[0] + 1: index[1]] + digits[index[1] + 1:]
                            if not digits:
                                return ''
                            if digits[0] != 0:
                                out = [str(num) for num in digits]
                                return ''.join(out)
                            else:
                                return '0'
            else:
                for k in range(n - 1, -1, -1):
                    if digits[k] % 3 == 2:
                        digits = digits[: k] + digits[k + 1:]
                        if not digits:
                            return ''
                        if digits[0] != 0:
                            out = [str(num) for num in digits]
                            return ''.join(out)
                        else:
                            return '0'
                index = []
                for k in range(n - 1, -1, -1):
                    if digits[k] % 3 == 1:
                        index.append(k)
                        if len(index) == 2:
                            index.reverse()
                            digits = digits[: index[0]] + digits[index[0] + 1: index[1]] + digits[index[1] + 1:]
                            if not digits:
                                return ''
                            if digits[0] != 0:
                                out = [str(num) for num in digits]
                                return ''.join(out)
                            else:
                                return '0'


data = Solution()
digits = [8, 1, 9]
print(data.largestMultipleOfThree(digits))
